package org.chengn.level_hard.context1349;

/**
 * @Title: Context1349
 * @Author ChengN
 * @Package org.chengn.level_hard.context1349
 * @Date 2023/12/26 21:14
 * @description 参加考试的最大学生数
 */
public class Context1349 {
    public int maxStudents(char[][] seats) {
        int m = seats.length;
        int n = seats[0].length;

        int[][] grid = new int[m][1 << n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                int maxVal = 0;
                if (i > 0) {
                    for (int k = 0; k < 1 << n; ++k) {
                        if ((j << 1 & k) == 0 && (j >> 1 & k) == 0) {
                            maxVal = Math.max(maxVal, grid[i - 1][k]);
                        }
                    }
                }
                grid[i][j] = maxVal + getVal(j, seats[i]);
            }
        }

        int result = 0;
        for (int i = 0; i < 1 << n; ++i) {
            result = Math.max(result, grid[m - 1][i]);
        }
        return result;
    }

    public int getVal(int c, char[] seats) {

        if ((c & c << 1) > 0 || (c & c >> 1) > 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < seats.length; ++j) {
                if (seats[j] == '#' && (1 << j & c) > 0) {
                    return 0;
                }
            }
            if ((c & 1 << i) > 0) {
                res++;
            }
        }
        return res;
    }
}
